8213. Штанги

В Вашем местном спортзале имеются n штанг и m тарелок. Чтобы подготовить вес для подъема, Вы должны выбрать одну штангу, имеющую две стороны. Затем Вы загружаете каждую сторону (возможно, пустым) набором пластин. По соображениям безопасности пластины с каждой стороны должны в сумме давать одинаковый вес. Какие значения весов доступны для подъема?

Вход. Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 14).

Вторая строка содержит n целых чисел b₁, ..., b_n (1 ≤ b_i ≤ 10⁸) – веса штанг в граммах.

Третья строка содержит m целых чисел p₁, ..., p_m (1 ≤ p_i ≤ 10⁸) – вес пластин в граммах.

Выход. Выведите отсортированный список всех возможных различных весов в граммах. Каждый вес следует выводить в одной строке.

Пример входа	Пример выхода
2 5 100 110 5 5 1 4 6	100 110 112 120 122 130

РЕШЕНИЕ

динамическое программирование - маски

Анализ алгоритма

Переберем все подмножества I пластин P. Для каждого подмножества пластин I вычислим сумму их весов в sum[I].

Переберем все подмножества I всех множеств пластин P. Если для множества I пластин имеется такое подмножество J Ì I, что суммарный вес пластин в J в два раза меньше суммарного веса пластин в I, то подмножество пластин из I можно одеть на штангу так чтобы с двух сторон были одинаковые веса (такими весами будут sum[J] и sum[I xor J]). Заносим вес sum[I] такого подмножества I во множество w.

Вес для подъема состоит из веса штанги и одетых на нее пластин. Для каждого веса штанги b[i] переберем все возможные веса x пластин из w. Все возможные веса для подъема b[i] + x занесем в результирующее множество res.

Реализация алгоритма

Объявим рабочие массивы.

#define MAX 16

int b[MAX], p[MAX], sum[1 << MAX];

Читаем входные данные – веса штанг и пластин.

scanf("%d %d", &n, &m);

for (i = 0; i < n; i++)

scanf("%d", &b[i]);

for (i = 0; i < m; i++)

scanf("%d", &p[i]);

Перебираем все подмножества I пластин P. Для каждого подмножества пластин I вычисляем сумму их весов в sum[I].

for (i = 0; i < 1 << m; i++)

for (j = 0; j < m; j++)

if (i & (1 << j)) sum[i] += p[j];

Перебираем все подмножества I всех множеств пластин P. Если для множества I пластин имеется такое подмножество J Ì I, что суммарный вес пластин в J в два раза меньше суммарного веса пластин в I, то подмножество пластин из I можно одеть на штангу так чтобы с двух сторон были одинаковые веса (такими весами будут sum[J] и sum[I xor J]). Заносим вес sum[I] такого подмножества I во множество w.

for (i = 1; i < 1 << m; i++)

{

int su = sum[i];

for (j = i; j > 0; j = (j - 1) & i)

if (sum[j] * 2 == su)

{

w.insert(su);

break;

}

}

Вес для подъема состоит из веса штанги и одетых на нее пластин. Для каждого веса штанги b[i] переберем все возможные веса x пластин из w. Все возможные веса для подъема b[i] + x занесем в результирующее множество res.

for (i = 0; i < n; i++)

{

res.insert(b[i]);

for (int x : w)

res.insert(b[i] + x);

}

Выводим ответ – отсортированный список всех возможных различных весов.

for (int x : res)

printf("%d\n", x);